package lc;

import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class Ex1301 {
    class Solution {
        public int[] pathsWithMaxScore(List<String> board) {
            int n = board.size();
            char[][] chs = new char[n][];
            for (int i = 0; i < n; i++) {
                chs[i] = board.get(i).toCharArray();
            }
            int[][] f = new int[n][n];
            int[][] path = new int[n][n];
            //你可以向上、向左或者左上方移动
            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i == n - 1 && j == n - 1) {
                        f[i][j] = 0; //S在(n - 1, n - 1)位置。
                        path[i][j] = 1;
                        continue;
                    } 
                    if (chs[i][j] == 'X') {
                        f[i][j] = -1;
                    } else { //"E23","2X2","12S"
                        if (i == n - 1) {
                            f[i][j] = f[i][j + 1] < 0 ? -1 : f[i][j + 1] + (chs[i][j] - '0');
                            path[i][j] = 1;
                        } else if (j == n - 1) {
                            f[i][j] = f[i + 1][j] < 0 ? -1 : f[i + 1][j] + (chs[i][j] - '0');
                            path[i][j] = 1;
                        } else {
                            int max = Math.max(f[i + 1][j], Math.max(f[i][j + 1], f[i + 1][j + 1]));
                            if (max < 0) {
                                f[i][j] = -1;
                            } else {
                                if (i == 0 && j == 0) {
                                    f[i][j] = max;
                                } else {
                                    f[i][j] = max + chs[i][j] - '0';
                                }
                                if (max == f[i + 1][j]) {
                                    path[i][j] += path[i + 1][j];
                                }
                                if (max == f[i][j + 1]) {
                                    path[i][j] += path[i][j + 1];
                                }
                                if (max == f[i + 1][j + 1]) {
                                    path[i][j] += path[i + 1][j + 1];
                                } 

                            }
                        }
                    }
                }
            }

            System.out.println(Arrays.deepToString(f));;

            if (f[0][0] < 0) {
                 return new int[]{0, 0};
            }

            return new int[]{f[0][0], path[0][0]};
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        List<String> board = Arrays.asList("E23","2X2","12S");
        System.out.println(Arrays.toString(s.pathsWithMaxScore(board)));
    }
}